package com.zyk.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author zhangsan
 * @date 2021/4/16 13:27
 */
public class C402 {

    // 贪心 + 单调栈实现
    // 贪心策略: 425, 三个数, 保留四: 42, 45,删除4: 25. 若要使得剩下的数字最小，需要保证靠前的数字尽可能小。
    // 上边的贪心策略可以保证单调性, 所以用单调栈来做, 因为最后取字符的时候又要从头开始拼接也就是栈底~栈顶. 所以使用双端队列既能做栈,又可做队列.
    public static String removeKdigits(String num, int k) {
        if (num.length() == k) return "0";
        else if (k <= 0) return num;
        char[] str = num.toCharArray();
        Deque<Character> deque = new ArrayDeque<>(str.length);
        for (int i = 0; i < str.length; i++) {
            // 如果栈顶必当前字符大, 直接删除掉那个字符.
            while (k > 0 && !deque.isEmpty() && deque.peekLast() > str[i]) {
                deque.pollLast();
                k--;
            }
            deque.addLast(str[i]);
        }
        for (int i = 0; i < k; i++)
            deque.pollLast();   // 如果还没删够, 直接继续删

        StringBuilder sb = new StringBuilder();
        boolean leadingZero = true;
        while (!deque.isEmpty()) {
            char digit = deque.pollFirst();
            if (leadingZero && digit == '0') continue;
            leadingZero = false;
            sb.append(digit);   // 从栈顶~栈尾拼接
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }

    // for test
    public static void main(String[] args) {
        String str = "1432219";
        int k = 3;
        System.out.println(removeKdigits(str, k));
    }

}
